<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
</head>

<body>
  <script>
    const arr = [5, 4, 9, 7, 8, 1, 3, 2]

    const sortArr = []; // 按照堆的结构进行数据存储

    let res = [] // 存储最终排序好的元素
    // 进堆操作
    for (let i = 0; i < arr.length; i++) {
      // 进堆
      sortArr.push(arr[i])
      // 检测
      checkChangeElement(i)
    }
    // 检查变动的元素
    // cindex表示变动元素的索引
    function checkChangeElement(cindex) {
      let num = cindex + 1; // 获取该变动元素的编号
      let pnum = Math.floor(num / 2) //获取该变动元素的父节点的编号
      if (pnum < 1) { // 如果父节点不存在，则停止
        return;
      }
      let index = pnum - 1; // 得到变动元素的父节点的索引
      if (sortArr[index] > sortArr[cindex]) { // 比较变动元素和其父节点的数值大小，不符合则交换位置
        [sortArr[cindex], sortArr[index]] = [sortArr[index], sortArr[cindex]]
        checkChangeElement(index);
      }
    }
    // 出堆操作
    function popHeap() {
      if (sortArr.length === 0) { // 如果堆中无元素，就停止操作
        return;
      }
      res.push(sortArr.shift()); // 把堆顶元素取出，并放入res中
      for (let i = 0; i < sortArr.length; i++) { // 调整剩余元素满足堆结构
        let num = i + 1; // 遍历到当前的一个节点，当做父节点，获取该节点的编号
        let l = i * 2; // 获取左子节点
        let r = i * 2 + 1; // 获取右子节点
        if (l > sortArr.length && r > sortArr.length) { // 编号num的节点是叶子节点
          continue;
        }
        if (r > sortArr.length && l <= sortArr.length) { // 编号num的节点的左子节点存在，右子节点不存在
          if (sortArr[l - 1] < sortArr[num - 1]) {// 比较父节点和左子节点的大小
            [sortArr[num - 1], sortArr[l - 1]] = [sortArr[l - 1], sortArr[num - 1]] // 交换元素的位置
          }
          continue
        }
        if (sortArr[l - 1] < sortArr[num - 1] && sortArr[l - 1] <= sortArr[r - 1]) { // 左右子节点都存在，左子节点小
          [sortArr[num - 1], sortArr[l - 1]] = [sortArr[l - 1], sortArr[num - 1]] // 进行位置交换的操作
        } else if (sortArr[r - 1] < sortArr[num - 1] && sortArr[r - 1] <= sortArr[l - 1]) { // 左右子节点都存在，右子节点较小
          [sortArr[num - 1], sortArr[r - 1]] = [sortArr[r - 1], sortArr[num - 1]] // 进行位置交换的操作
        }
      }
      popHeap(); // 继续出堆的操作
    }
    popHeap()


  </script>
</body>

</html>